Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Solution:

  1. public class Solution {
  2.   public boolean search(int[] A, int target) {
  3.     return bsearch(A, target, 0, A.length - 1);
  4.   }
  6.   private boolean bsearch(int[] A, int target, int lo, int hi) {
  7.     if (lo > hi) {
  8.       return false;
  9.     }
  11.     int mid = lo + (hi - lo) / 2;
  13.     if (A[mid] == target) {
  14.       return true;
  15.     }
  17.     if (A[lo] < A[mid]) {
  18.       if (target >= A[lo] && target < A[mid]) {
  19.         return bsearch(A, target, lo, mid - 1);
  20.       } else {
  21.         return bsearch(A, target, mid + 1, hi);
  22.       }
  23.     } else if (A[lo] > A[mid]) {
  24.       if (target > A[mid] && target <= A[hi]) {
  25.         return bsearch(A, target, mid + 1, hi);
  26.       } else {
  27.         return bsearch(A, target, lo, mid - 1);
  28.       }
  29.     } else {
  30.       return bsearch(A, target, lo + 1, hi);
  31.     }
  32.   }
  33. }